package 剑指Offer_day06;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 *剑指 Offer 32 - II. 从上到下打印二叉树 II
 *
 * 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
 *
 * 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
 *
 *
 *
 * 例如:
 * 给定二叉树:[3,9,20,null,null,15,7],
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * 返回其层次遍历结果：
 *
 * [
 *   [3],
 *   [9,20],
 *   [15,7]
 * ]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 */
public class Offer_32_II {

    public List<List<Integer>> levelOrder(TreeNode root) {

        if (root==null){

            return new ArrayList<>();

        }

//        使用队列 保存每一层的节点 每一层都保存在一个数组中
        LinkedList<ArrayList<TreeNode>> linkedList = new LinkedList<>();

        //将头节点 放到对列中
        ArrayList<TreeNode> arrayList = new ArrayList<>();
        arrayList.add(root);
        linkedList.add(arrayList);

        //用来保存结果
        List<List<Integer>> result = new ArrayList<>();

        //队列不为空
        while (!linkedList.isEmpty()){

            //从队列中 弹出一个集合 当前层的所有的节点
            ArrayList<TreeNode> list = linkedList.poll();

            //用于保存 当前层的value
            ArrayList<Integer> integers = new ArrayList<>();

            //用来保存 下一层的所有的节点
            ArrayList<TreeNode> treeNodes = new ArrayList<>();

            //开始遍历 当前层的节点
            for (TreeNode treeNode : list) {
                if(treeNode!=null){
                    integers.add(treeNode.val);
                   if (treeNode.left!=null)treeNodes.add(treeNode.left);
                   if (treeNode.right!=null)treeNodes.add(treeNode.right);
                }
            }

            //下一层的节点 放入队列
           if (!treeNodes.isEmpty())linkedList.add(treeNodes);

           //这一层的结果集合 放入集合
            if(!integers.isEmpty()) result.add(integers);

        }

        return result;

    }


    public static void main(String[] args) {

        //[3,9,20,null,null,15,7]

        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode9 = new TreeNode(9);
        TreeNode treeNode20 = new TreeNode(20);
        TreeNode treeNode15 = new TreeNode(15);
        TreeNode treeNode7 = new TreeNode(7);
//        TreeNode treeNode3 = new TreeNode(3);

        treeNode3.left = treeNode9;
        treeNode3.right = treeNode20;

        treeNode20.left = treeNode15;
        treeNode20.right = treeNode7;

        Offer_32_II offer_32_ii = new Offer_32_II();

        List<List<Integer>> lists = offer_32_ii.levelOrder(treeNode3);

        System.out.println(lists);


    }

}

